package main.leetcode.clockin.June;

/**
 * 67. 二进制求和
 *
 * <p>给你两个二进制字符串，返回它们的和（用二进制表示）。
 *
 * <p>输入为 非空 字符串且只包含数字 1 和 0。
 *
 * <p>示例 1: 输入: a = "11", b = "1" 输出: "100"
 *
 * <p>示例 2: 输入: a = "1010", b = "1011" 输出: "10101"
 *
 * <p>提示：每个字符串仅由字符 '0' 或 '1' 组成。 1 <= a.length, b.length <= 10^4 字符串如果不是 "0" ，就都不含前导零。
 */
public class day23 {
    public static void main(String[] args) {
        System.out.println(new day23().addBinary("11011", "1010"));
        System.out.println(new day23().addBinary("1010", "1011"));
        System.out.println(new day23().addBinary("0", "0"));
    }

    //    public String addBinary(String a, String b) {
    //        if (a.isEmpty()) {
    //            return b;
    //        }
    //        if (b.isEmpty()) {
    //            return a;
    //        }
    //        int m = a.length();
    //        int n = b.length();
    //        if (m < n) {
    //            m = m + n - (n = m);
    //            String tmp = a;
    //            a = b;
    //            b = tmp;
    //        }
    //        int d = m - n;
    //        int carry = 0;
    //        StringBuilder res = new StringBuilder();
    //        for (int i = m - 1; i >= d; --i) {
    //            int sum = carry;
    //            sum += a.charAt(i) - '0' + b.charAt(i - d) - '0';
    //            res.append(sum % 2);
    //            carry = sum / 2;
    //        }
    //        for (int i = d - 1; i >= 0; --i) {
    //            int sum = carry;
    //            sum += a.charAt(i) - '0';
    //            res.append(sum % 2);
    //            carry = sum / 2;
    //        }
    //        if (carry == 1) {
    //            res.append('1');
    //        }
    //        return res.reverse().toString();
    //    }

    public String addBinary(String a, String b) {
        if (a.isEmpty()) {
            return b;
        }
        if (b.isEmpty()) {
            return a;
        }
        int m = a.length();
        int n = b.length();
        int carry = 0;
        StringBuilder res = new StringBuilder();
        for (int i = m - 1, j = n - 1; i >= 0 || j >= 0; --i, --j) {
            int sum = carry;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            res.append(sum % 2);
            carry = sum / 2;
        }
        if (carry == 1) {
            res.append('1');
        }
        return res.reverse().toString();
    }
}
